package algorithms.sorting

/**
 * [Quicksort 1 - Partition](https://www.hackerrank.com/challenges/quicksort1)
 */
// Complete the quickSort function below.
fun quickSort(arr: Array<Int>): Array<Int> {
    fun partition(arr1: Array<Int>, start: Int, end: Int) {
        if (end - start < 2) {
            return
        }
        var temp: Int
        var cursor = start
        val p = arr1[start]
        var pCount = 1

        for (i in start + 1 until end) {
            temp = arr1[i]
            if (temp <= p) {
                for (j in i downTo cursor + 1) {
                    arr[j] = arr[j - 1]
                }
                arr[cursor] = temp
                if (temp == p) {
                    pCount++
                } else {
                    cursor++
                }
            }
        }
//        partition(arr1, start, cursor)
//        partition(arr1, cursor + pCount, end)
    }

    partition(arr, 0, arr.size)

    return arr
}